package day_2022_7_to_8.day48;

/**
 * @author haomin
 * @date 2022/08/05 20:44
 **/
public class Day21_3_Num16_ThreeSumClosest {
    public int threeSumClosest(int[] nums, int target) {
        bubbleSort(nums);
        int res = Integer.MAX_VALUE;
        for (int i = 0; i < nums.length; i++) {
            int j = i+1,k = nums.length-1;
            int sum;
            while (j<k){
                sum = nums[i]+nums[j]+nums[k];
                if(Math.abs(target-sum) < Math.abs(target-res)) res = sum;
                if(sum > target) k--;
                else if(sum < target) j++;
                else return res;
            }
        }
        return res;
    }

    private static void bubbleSort(int[] nums) {
        for (int i = 0; i < nums.length; i++) {
            for (int j = 0; j < nums.length-i-1; j++) {
                if(nums[j] > nums[j+1]){
                    int temp = nums[j];nums[j] = nums[j+1];nums[j+1] = temp;
                }
            }
        }
    }


    // 回溯超时
    class Solution2 {
        public int res = Integer.MAX_VALUE;
        public int threeSumClosest(int[] nums, int target) {
            dfs(nums,0,0,0,target);
            return res;
        }
        private void dfs (int[] nums,int start,int sum,int count,int target){
            if(count == 3){
                if(Math.abs(target-sum) < Math.abs(target-res)) {
                    res = sum;
                }
                return;
            }
            for(int i = start;i < nums.length;i++){
                sum += nums[i];count++;
                dfs(nums,i+1,sum,count,target);
                sum -= nums[i];count--;
            }
        }
    }
}